HJ85 最长回文子串

本节目标：理解“HJ85 最长回文子串”的核心思路，并能把它用于实际开发或面试表达。 描述 给定一个仅包含小写字母的字符串，求它的最长回文子串的长度。 所谓回文串，指左右对称的字符串。 所谓子串，指一个字符串删掉其部分前缀和后缀（也可以不删）的字符串

数据范围：字符串长度 1≤s≤350 进阶：时间复杂度： O(n) ，空间复杂度： O(n) 输入描述： 输入一个仅包含小写字母的字符串 输出描述： 返回最长回文子串的长度 示例1 输入： cdabbacc ==复制== 输出： 4 ==复制== 说明： abba为最长的回文子串

寻找字符串中最长回文子串的长度是一个经典的字符串处理问题。一个常见的方法是使用动态规划，但其时间复杂度和空间复杂度通常是O(n^2)，这并不满足题目进阶要求的O(n)。满足O(n)时间复杂度的算法是Manacher算法。

Manacher算法是一个用来寻找字符串中最长回文子串的高效算法，时间复杂度为O(n)。它通过在字符串的每两个字符之间插入一个分隔符（通常是一个在字符串中不会出现的字符，例如#），来解决奇数长度和偶数长度回文子串的处理不一致问题。

下面是Manacher算法的简单实现：

def find_longest_palindrome(s):

准备经过格式化的字符串，用于简化回文查找的边界处理

formatted_str = "#".join("^{}$".format(s))

计算格式化后字符串的长度

length_of_formatted_str = len(formatted_str)

初始化数组，用于存放以每个字符为中心的最大回文半径

palindrome_radius = [0] * length_of_formatted_str

初始化当前探索的回文中心和右边界

center_of_palindrome, right_bound_of_palindrome = 0, 0

遍历格式化后的字符串，除去首尾的特殊字符

for i in range(1, length_of_formatted_str - 1):

如果当前位置在已知最大回文右边界内，则利用对称性初始化回文半径

if right_bound_of_palindrome > i: palindrome_radius[i] = min( right_bound_of_palindrome - i, palindrome_radius[2 * center_of_palindrome - i])

尝试扩展以当前字符为中心的回文区域

while formatted_str[i + palindrome_radius[i] + 1] == formatted_str[i - palindrome_radius[i] - 1]: palindrome_radius[i] += 1

更新当前探索的回文中心和右边界

if i + palindrome_radius[i] > right_bound_of_palindrome: center_of_palindrome, right_bound_of_palindrome = i, i +
palindrome_radius[i]

找出并返回最长回文的长度

max_palindrome_radius = max(palindrome_radius)

最长回文的实际长度需要剔除插入的'#'字符

longest_palindrome_length = max_palindrome_radius return longest_palindrome_length

读取输入字符串

input_str = input()

计算并打印最长回文子串的长度

print(find_longest_palindrome(input_str))

请注意，上面的实现虽然在算法逻辑上是正确的，但直接运行可能会遇到语法错误或者逻辑上的小错误，因为Manacher算法的完整实现涉及到很多细节处理，上面的代码主要用于演示算法的核心思想。在实际应用中，你可能需要根据具体语言和环境调整实现细节。

该算法的核心在于利用回文的对称性质以及维护一个当前已知的最大回文右边界，通过这些信息减少不必要的比较，从而达到O(n)的时间复杂度。

t = '#'.join('^{}$'****.format(s)) 这行代码是manacher函数中用于预处理输入字符串s的一部分，目的是为了方便之后进行回文子串的查找。具体来说，这行代码做了以下几件事：

t = "#".join("^{}$".format(s))

1. format(s): 首先，通过"{}"占位符将输入字符串s嵌入到"{}"中，这一步其实就是直接返回字符串s本身，不过这样做为后续的添加首尾特殊字符^和$做准备。

2. "^{}$".format(s): 在字符串s的首尾分别添加了^和$两个特殊字符。这两个特殊字符在原字符串中是不会出现的，它们被用作哨兵字符，分别标记处理后字符串的开始和结束。添加这两个字符的目的是为了在后续的回文扩展中处理边界情况，避免索引超出字符串的范围。

3. "#".join(...): 将处理后的字符串中的每个字符（包括首尾的特殊字符^和$）之间插入#字符。这一步的目的是将原字符串转化为一个新的形式，使得原字符串中的每个字符都被#包围，同时在两个相邻字符之间也插入了#。这样做的好处是，它允许算法以统一的方式处理奇数长度和偶数长度的回文子串，因为插入#后，原字符串中的任何一个回文子串在新字符串中的表示都将是奇数长度的。

综上，这行代码通过在输入字符串s的每两个字符之间（以及首尾）插入#，并在首尾添加特殊的哨兵字符，生成了一个新的字符串t。这个字符串t是后续进行回文子串查找的基础。通过这样的预处理，Manacher算法能够有效地在线性时间内找到最长的回文子串。